/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ia_psr.algoritmos;

/**
 *
 * @author Rubén Avalos Elvira y Fabiana Celiberti Tapie
 */
import ia_psr.problemas.IConjunto;
import ia_psr.problemas.IProblema;
import ia_psr.problemas.Variable;
import ia_psr.graph.Nodo;
import ia_psr.graph.GrafoRestricciones;
import ia_psr.graph.NodoPSR;
public class PSRBacktracking implements IAlgoritmo {
    protected GrafoRestricciones g;
    protected IConjunto variables;
    protected boolean solucion;
    protected int nodosExpandidos;
    protected int variablesExpandidas;
    protected double executionTime;
    protected boolean resultado;

    public PSRBacktracking() {
        resultado = false;
    }

    public boolean hasSolution() {
        return solucion;
    }

    public void initGrafo() {
        g.resetAllNodos();
    }
    
    public GrafoRestricciones resolver(GrafoRestricciones g, IConjunto c) {
        //boolean resultado;
        this.g = (GrafoRestricciones)g;
        this.variables = c;
        solucion = false;
        nodosExpandidos = 0;
        variablesExpandidas = 0;
        initGrafo();

        executionTime = System.nanoTime();
        resultado = iResolver(variables.elementos.get(0));
        executionTime = (System.nanoTime() - executionTime);///1000000000;

        if (!resultado) {
            System.out.println("No se ha encontrado solucion");
        }

        return this.g;
    }

    // Devuelve primer nodo sin asignar
    public NodoPSR nextNode() {
        for(Nodo nodo : g.getNodos()) {
            NodoPSR n = (NodoPSR)nodo;
            if (n.valor.getValue() == null) {
                return n;
            }
        }
        return null;
    }

    protected boolean iResolver(Variable v) {
        if (solucion)
            return true;
        int resultadoComprobacion = g.estadoValido();
        if (resultadoComprobacion == IProblema.VALIDO) {
            solucion = true;
            return true;
        }
        if (resultadoComprobacion == IProblema.NO_VALIDO)
            return false;

        NodoPSR n = nextNode();// Aplicacion de la heuristica 1
        ++nodosExpandidos;

        boolean resultado;

        for (Variable var : variables.elementos) {
            ++variablesExpandidas;
            g.asignVariable(n, var);
            resultado = iResolver(var);
            if (resultado)
                return true;
            else {
                g.resetNodo(n);
            }
        }
        return false;

    }

    public int getNodosExpandidos() {
        return nodosExpandidos;
    }

    public int getVariablesExpandidas() {
        return variablesExpandidas;
    }

    public double getExecutionTime() {
        return executionTime;
    }

}
